package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 113. 路径总和 II
 * @date 2025/5/22 17:10
 */
public class E113 {

    /**
     * 方法一：dfs+回溯+双端队列做栈
     *
     * @param root      根节点
     * @param targetSum 目标和
     * @return 路径集合
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(root, result, targetSum, new LinkedList<>());
        return result;
    }

    /**
     * dfs
     *
     * @param root      根节点
     * @param result    结果集
     * @param targetSum 目标和
     * @param deque     栈
     */
    private void dfs(TreeNode root, List<List<Integer>> result, int targetSum, Deque<Integer> deque) {
        if (root == null) return;
        deque.offerLast(root.val);
        if (root.left == null && root.right == null && root.val == targetSum) {
            result.add(new ArrayList<>(deque));
            deque.pollLast();
            return;
        }
        dfs(root.left, result, targetSum - root.val, deque);
        dfs(root.right, result, targetSum - root.val, deque);
        deque.pollLast();
    }
}
